第五回 アルゴリズム実技検定
70点、中級でした。
初めて受験した第三回もその次の第四回も中級で、今度こそ上級になりたいなとPAST過去問練習202012して臨んだのだけども、点数はむしろ下がってしまった。 https://gyazo.com/85686f0f9aea6837a7ee2e7a46ef64d5
受験中に考えたことを書いておく。まだ過去問としての公開がされてないので問題文や解説を確認できない。個別の問題の詳しい解法はそれが出てから別途書く。
過去問の公開がされたので順にやっていく
E〜の解説
HのTLEの原因確認
Jの解説見ないでのときなおし
LMNOの解説の確認
A〜D
特に何もメモせずに淡々と解いた
https://gyazo.com/96531e5dba571b147d99cf54cec7253f
素朴に全探索すれば良い
はみださないように全探索するために、スタンプでない側にスタンプの幅分の番兵をつけた 番兵をつけるコード自体は既に書いてあった
回転は想定してなかったので今回新たに書いた
回転時に縦横の長さが交換される、スタンプの側だけを交換するべきだが取り違えててWAした
https://gyazo.com/82689f73ea9cacb95a4584a9b4618956
2 ** 14 == 16384
14 * 13 * 12 == 364
これは全探索して良いサイズ
問題条件を勘違いしてWA
一触即発状態での「既に混ぜた薬品の数」ではない
「一触即発状態のルールの数」でもない
「一触即発状態のルールの、まだ追加してない薬品」の集合のサイズ
https://gyazo.com/3790c397c786b793094fb8a7167295bd
グラフを作って各頂点を始点として「すべての頂点を通るパス」をDFS
長さが1の時、グラフにならないのがコーナーケース
ここまでで1時間25分。ここでまず残りすべての問題に目を通すことにした。下記の「初回考察」がそれ。
https://gyazo.com/f0e4b1e3e154ed74f38484fa80a6fd5a
初回考察
動かせるか判定
グラフを構築して、各始点から「ゴールにたどり着けるか」をDFS
頂点数10^6、大丈夫？
スタートがたくさん、ゴールは一つ
グラフを逆辺で作っておき、ゴールを始点として到達可能頂点を探索する。
各頂点高々4本の辺しか持たないのでO(N)で間に合う
考察完了
https://gyazo.com/01513f650068f7946cc04b839444666a
初回考察
標高の高い方から低い方へしか動けない
有向グラフ
ゴールがたくさん
コスト0の辺で束ねる？
後者をやって、ダメなら前者にしよう
考察完了
https://gyazo.com/a30032ca3d2b05fc4156aed0ed48365c
初回考察
素朴に出力はできない
各繰り返しのブロックのサイズを前計算しておけば、クエリの値を徐々に剰余とっていくことで解決するだろう
考察完了
https://gyazo.com/6479e86b1c951eb67508032cd297072f
初回考察
残っている的が2^16
先の左右に同じ項がでてくるので整理して消去する必要がある。
考察完了
https://gyazo.com/9d3a4c94bb870908ddb459d35f181fb0
初回考察
出現箇所は複数あり、どちらを優先して消すかによって最良の結果になったりならなかったりする
https://gyazo.com/b7c90ebc80943d64f71cf6ecc519c5df
うーん、なんらかのグリーディな決め方が存在する？
オーバーラップしてない場合にはどちらからやっても変わらない？
それでも最悪33個オーバーラップしてる。33の階乗は無理
非決定オートマトンでいい感じに処理できないかな
保留
https://gyazo.com/d4601d3337d3e2a1f3a3e17ce6c0b8da
初回考察
切る切らない2^Nは、Nが10^5とか大きいのでダメ
2NのDPになる？
無理そう
一旦最大限に長く刻んで、その刻みを1つずつ前に移動するスタイルではどうか
しゃくとり法的な、解のありそうなところだけを探索するアプローチ
下限が徐々に上がっていく、下限より小さくなるところは探索しなくても良いので割と探索空間小さめにならないかなー
https://gyazo.com/c0b27c17755f5bd753462bf179457248
初回考察
バスの辺に年齢の上限、下限があり、与えられた年齢がその範囲に収まっているときだけ辺が存在するとみなして到達可能範囲を求める問題
年齢軸を時間軸にする
下限でつなぎ、上限で外せば良い
クエリは先読みして、混ぜてソートする
PAST2NではRange Addだったけど、今回はそうではない、どうするか？ 繋がってる範囲の右端と左端が高速に得られれば良い
右端を持つフェニック木と左端を持つフェニック木を用意すれば良い
ある位置が与えられた時に、そこより左にある最も近い左端を見つけるのは二分探索で対数オーダー
見つけた左端より右で最も近い右端を見つければ範囲がわかる
クエリで与えられた位置がその範囲に入ってれば、それが答え
考察完了
https://gyazo.com/9d380fa7f1c141460e331b7a7e7f8144
初回考察
プッシュでもプルでも最悪10^5になるので10^5回のクエリでは破綻する
(補足: 通知発生時に受領者の値を変更する「プッシュ」の場合、フレンドの10^5人いる人が通知を10^5回送るとダメ。逆に通知確認の時にフレンドの誰が送ったか確認しにいく「プル」の場合はフレンドの多い人が通知確認をしまくるとダメ)
フレンドがルートN以上の人の処理だけ遅延させる
こういう人は高々ルートN人
通知確認時にこれらの人xだけプルする
xの発生させた総通知数をxが持つ
yがxから受信した総数をyが持つ。高々ルートN
この二つを引けばxからの新しい通知の数がわかる
考察完了
一通り考察して、残り3時間。
Lがまったくわからない
M, Oが解けそうな気がするが「一見解けそうに見えて、解いてみると見落としが発見されるパターン」だろうなと思う
コンテストと違って難しい問題を優先して解いてもレートが上がるわけじゃないからな(むしろ点数は低い)
頭から順番に解いて、改めてLを見返す方針でやろう
この後の出来事
H、18分で提出してWA、修正するも3回TLE、35分まで掛かって解決しないので保留して次へ
I、ダイクストラする、9分でAC
J、落ち着いて実装するべきだったのに混乱してしまう
一つズレのバグを解決してようやくサンプルが通ったのが56分後
しかしTLE
繰り返しの単位になる文字列を切り出して使ってたけども、元の文字列のどこから開始するかだけを待てば良いと考える
さらに16分使ってまたTLE、それどころかMLEもある
どういうことか？！
例えば9がたくさん続いた時に「繰り返しブロックのサイズ」はとても大きな数になる、これを意識せずにそのままやってたのが問題
リアルタイムでは「まったく方針が間違ってたということか？」と思って諦めた
一晩寝て起きたら、クエリとして渡される数が10^15以下だと制限されてるので、それを超えた時点で文字列のパース処理を打ち切ってしまって良いと気づいた
K、期待値DPする、19分でAC
この時点で残り45分、方針の立ってないLに挑戦できる状態ではない、TLEになってるHを解決しよう
H、30分使ってさらに3回TLEして、残り15分でようやくAC
グラフを陽に構築しないスタイルに書き換えた
DFSを再帰呼び出ししないバージョンにした
時間で整理すると
72分使って無得点のJが酷い
80分使ってようやくACしたHもいまいち
Iが9分、Kが19分なのと比べると落差が激しい